//
//  92. 反转链表II.swift
//  Top600
//
//  Created by rjb on 2021/8/10.
//

import Foundation
class Solution92 {
    func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
        // 找到pre
        let vHead: ListNode? = ListNode(-1)
        vHead?.next = head
        var pre = vHead
        for _ in 0..<left - 1 {
            pre = pre?.next
        }
        
        // 逐个以头插法添加
        // 整个的插入过程是以cur为着陆点
        let cur = pre?.next
        var next: ListNode?
        for _ in 0..<right - left {
            next = cur?.next // 记录要插入的节点
            cur?.next = next?.next
            next?.next = pre?.next
            pre?.next = next
        }
        return vHead?.next
    }
    
    static func test() {
        let solution = Solution92()
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        let node3 = ListNode(3)
        let node4 = ListNode(4)
        let node5 = ListNode(5)
        
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        
        let result = solution.reverseBetween(node1, 2, 4)
        print(result)
    }
}
